/*
 * "git edit-tree" is a lightweight tree editor.
 *
 * Copyright (c) Jiang Xin, 2023
 */
#include "builtin.h"
#include "alloc.h"
#include "config.h"
#include "hash.h"
#include "hex.h"
#include "object-name.h"
#include "object-store.h"
#include "pathspec.h"
#include "parse-options.h"
#include "repository.h"
#include "strbuf.h"
#include "tree.h"

enum walk_tree_flags {
	MARK_TREE_DIRTY = (1 << 0),
};

/*
 * file_entry is a linked list, which is used to store
 * first level file entries of a tree.
 */
struct file_entry {
	char *name;
	unsigned int mode;
	struct object_id oid;
	struct file_entry *next;
};

/*
 * Git tree object has file entries and subtree entries.
 * The lazy_tree also has two linked list to store first
 * level subdirs (*dir_entry) and files (*file_entry).
 */
struct lazy_tree {
	char *name;
	struct tree tree;
	unsigned int loaded : 1, dirty : 1;

	/* first level subtree and files of current tree */
	struct lazy_tree *dir_entry;
	struct file_entry *file_entry;

	/* linked list of lazy_tree for one dir_entry */
	struct lazy_tree *next;
};

struct object_entry {
	struct object_id oid;
	unsigned int mode;
	char *path;
};

struct entry_context {
	struct strbuf find_path;
	struct object_entry *entry;
};

/*
 * entries is an array of treeent, to store entries in a tree,
 * and will be used to rehash the tree.
 */
static struct treeent {
	char *name;
	int len;
	struct object_id *oid;
	unsigned mode;
} * *entries;

/* alloc is the number of treeent already allocated by calling ALLOC_GROW. */
static int alloc;

static const char *edit_tree_usage[] = {
	"git edit-tree [-z] [-f <input-file>] <tree-id>", NULL
};

static void free_one_file_entry(struct file_entry *head)
{
	if (head) {
		free(head->name);
		free(head);
	}
}

static void free_file_entry_list(struct file_entry *head)
{
	struct file_entry *tmp;
	while (head) {
		tmp = head;
		head = head->next;
		free_one_file_entry(tmp);
	}
}

static void free_tree_entry_list(struct lazy_tree *head);

static void free_one_tree_entry(struct lazy_tree *head)
{
	if (head) {
		free(head->name);
		free_tree_buffer(&head->tree);
		free_file_entry_list(head->file_entry);
		head->file_entry = NULL;
		free_tree_entry_list(head->dir_entry);
		head->dir_entry = NULL;
		free(head);
	}
}

static void free_tree_entry_list(struct lazy_tree *head)
{
	struct lazy_tree *tmp;
	while (head) {
		tmp = head;
		head = head->next;
		free_one_tree_entry(tmp);
	}
}

static void file_entry_sort(struct file_entry *entry)
{
	struct file_entry *p, *cur, *pre;
	struct file_entry *tmp;

	if (entry == NULL || entry->next == NULL)
		return;

	pre = entry->next;
	cur = pre->next;
	pre->next = NULL;

	while (cur) {
		p = cur;
		cur = cur->next;
		p->next = NULL;
		pre = entry;

		while (pre->next) {
			if (strcmp(pre->next->name, p->name) > 0) {
				tmp = pre->next;
				pre->next = p;
				p->next = tmp;
				break;
			}

			pre = pre->next;
		}

		if (!pre->next) {
			pre->next = p;
		}
	}
}

static int free_obj_entry(struct object_entry *entry)
{
	if (entry) {
		free(entry->path);
		free(entry);
	}

	return 0;
}

static int is_empty_obj_entry(struct object_entry *entry)
{
	if (is_null_oid(&entry->oid) && !entry->path && !entry->mode)
		return 1;
	return 0;
}

static struct lazy_tree *new_lazy_tree(const char *name,
				       const struct object_id *oid, int parse)
{
	struct lazy_tree *tree;

	tree = xcalloc(1, sizeof(*tree));
	tree->name = xstrdup(name);
	tree->dirty = 0;
	if (oid) {
		tree->tree.object.oid = *oid;
		if (parse)
			parse_tree_gently(&tree->tree, 1);
	}
	return tree;
}

/*
 * A place-holder tree is a new subdir we created to hold
 * files and subdirs. It's oid is not determined.
 */
static int is_place_holder_tree(struct lazy_tree *tree)
{
	if (is_null_oid(&tree->tree.object.oid))
		return 1;
	return 0;
}

/* fill_tree_entry is a callback function for read_tree() */
static int fill_tree_entry(const struct object_id *oid, struct strbuf *base,
			   const char *pathname, unsigned mode, void *context)
{
	struct lazy_tree *tree = context;
	enum object_type type = object_type(mode);

	if (type == OBJ_TREE) {
		struct lazy_tree *new;
		new = new_lazy_tree(pathname, oid, 1);
		if (tree->dir_entry) {
			new->next = tree->dir_entry->next;
			tree->dir_entry->next = new;
		} else {
			new->next = NULL;
			tree->dir_entry = new;
		}
	} else {
		struct file_entry *new;
		new = xcalloc(1, sizeof(struct file_entry));
		new->oid = *oid;
		new->mode = mode;
		new->name = xstrdup(pathname);

		if (tree->file_entry) {
			new->next = tree->file_entry->next;
			tree->file_entry->next = new;
		} else {
			new->next = NULL;
			tree->file_entry = new;
		}
	}
	return 0;
}

static int load_one_tree_entry(struct lazy_tree *tree)
{
	const struct pathspec pathspec = { 0 };

	if (tree->loaded)
		return 0;
	/*
	 * A place-holder tree is a new subdir we created to hold
	 * files and subdirs. The hash of the place-holder tree
	 * is not determined, and it is not in the repository either.
	 */
	if (is_place_holder_tree(tree))
		return 0;

	if (parse_tree(&tree->tree))
		return error("fail to parse tree: %s",
			     oid_to_hex(&tree->tree.object.oid));
	/*
	 * Parse the tree object (tree->tree) for one level, and call
	 * function "fill_tree_entry" to fill entries for the tree.
	 * File entries will be appended to tree->file_entry, and
	 * dir entries will be appended to tree->dir_entry.
	 */
	read_tree(the_repository, &tree->tree, &pathspec, fill_tree_entry,
		  tree);
	tree->loaded = 1;

	file_entry_sort(tree->file_entry);
	return 0;
}

/*
 * walk through root_tree to find a subtree which matches path in data.
 * The subtree found in root_tree will write back to cb_data.
 */
static int walk_tree(struct lazy_tree *root_tree, const char *path,
		     struct lazy_tree **endpoint, int flag)
{
	struct string_list list = STRING_LIST_INIT_DUP;
	struct lazy_tree *tree = root_tree;
	struct lazy_tree **subtree;
	int ret = 0;

	if (!path) {
		ret = error("it's insane to walk a null path");
		goto clean;
	}

	if (flag & MARK_TREE_DIRTY)
		root_tree->dirty = 1;

	string_list_split(&list, path, '/', -1);
	for (struct string_list_item *item = list.items;
	     item && item < list.items + list.nr; ++item) {
		/*
		 * Skip empty path, e.g.: for "a//b", an empty path
		 * between a and b.
		 */
		if (!*item->string)
			continue;

		/* load the tree we want to access */
		if (load_one_tree_entry(tree)) {
			ret = -1;
			goto clean;
		}

		/* walk file_entry to find D/F conflict */
		for (struct file_entry *fe = tree->file_entry; fe;
		     fe = fe->next) {
			if (!strcmp(fe->name, item->string)) {
				ret = error(
					"found a D/F conflict, cannot walk into '%s'",
					item->string);
				goto clean;
			}
		}

		/* walk dir_entry to find matched entry with p */
		for (subtree = &tree->dir_entry; *subtree;
		     subtree = &(*subtree)->next) {
			if (!strcmp((*subtree)->name, item->string))
				break;
		}

		/* create new tree as a place-holder if fail to find p. */
		if (!*subtree) {
			*subtree = new_lazy_tree(item->string, NULL, 0);
			/* tree not in the repository */
			(*subtree)->dirty = 1;
		}
		tree = *subtree;

		/* We walk into tree and want to make some changes  */
		if (flag & MARK_TREE_DIRTY)
			tree->dirty = 1;
	}

	/* Try to fill entries for the endpoint tree we found. */
	if (load_one_tree_entry(tree)) {
		ret = -1;
		goto clean;
	}
	if (endpoint)
		*endpoint = tree;

clean:
	string_list_clear(&list, 0);
	return ret;
}

static int read_entry(struct lazy_tree *root_tree, const char *path,
		       struct object_entry *obj)
{
	struct strbuf buf = STRBUF_INIT;
	struct lazy_tree *tree;
	char *p;
	int len, ret = 0;
	struct lazy_tree **tree_entry;
	struct file_entry **file_entry;

	len = strlen(path);
	while (len > 0 && path[len - 1] == '/')
		len--;
	while (len > 0 && path[len - 1] != '/')
		len--;
	strbuf_add(&buf, path, len);
	if (walk_tree(root_tree, buf.buf, &tree, MARK_TREE_DIRTY))
		return -1;

	strbuf_reset(&buf);
	p = (char *)path + len;
	len = strlen(p);
	while (len > 0 && p[len - 1] == '/')
		len--;
	strbuf_add(&buf, p, len);

	tree_entry = &tree->dir_entry;
	while (*tree_entry) {
		if (!strcmp(buf.buf, (*tree_entry)->name)) {
			obj->mode = S_IFDIR;
			obj->path = xstrdup(buf.buf);
			oidcpy(&obj->oid, &(*tree_entry)->tree.object.oid);
			goto cleanup;
		}

		tree_entry = &(*tree_entry)->next;
	}

	file_entry = &tree->file_entry;
	while(*file_entry) {
		if (!strcmp(buf.buf, (*file_entry)->name)) {
			obj->mode = (*file_entry)->mode;
			obj->path = xstrdup(buf.buf);
			oidcpy(&obj->oid, &(*file_entry)->oid);
			goto cleanup;
		}

		file_entry = &(*file_entry)->next;
	}

cleanup:
	strbuf_release(&buf);
	return ret;
}

static int is_empty_tree(struct lazy_tree *tree)
{
	struct lazy_tree *tree_entry;
	struct file_entry *file_entry;

	/*
	 * If has a valid tree-id (not a place_holder), and not loaded yet,
	 * that means it's a non-empty tree, and we have no interesting to
	 * travel it.
	 */
	if (!tree->loaded && !is_place_holder_tree(tree))
		return 0;

	for (file_entry = tree->file_entry; file_entry;
	     file_entry = file_entry->next)
		return 0;

	for (tree_entry = tree->dir_entry; tree_entry;
	     tree_entry = tree_entry->next) {
		if (!is_empty_tree(tree_entry))
			return 0;
	}

	return 1;
}

static int do_ls_tree(struct lazy_tree *tree, const char *parent_dir)
{
	struct strbuf full_path = STRBUF_INIT;
	struct strbuf mark = STRBUF_INIT;
	struct lazy_tree *tree_entry;
	struct file_entry *file_entry;

	if (parent_dir && *parent_dir)
		strbuf_addstr(&full_path, parent_dir);
	if (tree->name && *tree->name) {
		if (full_path.len)
			strbuf_addch(&full_path, '/');
		strbuf_addstr(&full_path, tree->name);
	}

	if (tree->dirty || !tree->loaded) {
		strbuf_addstr(&mark, " (");
		strbuf_addch(&mark, tree->dirty ? '!' : ' ');
		strbuf_addch(&mark, tree->loaded ? ' ' : '?');
		strbuf_addch(&mark, ')');
	}

	/* show this tree entry */
	fprintf(stderr, "%06o %s %*s %s%s\n", S_IFDIR,
		type_name(object_type(S_IFDIR)), (int)the_hash_algo->hexsz,
		!is_place_holder_tree(tree) ?
			oid_to_hex(&tree->tree.object.oid) :
			"",
		full_path.len ? full_path.buf : ".", mark.buf);

	for (tree_entry = tree->dir_entry; tree_entry;
	     tree_entry = tree_entry->next) {
		if (!is_empty_tree(tree_entry))
			do_ls_tree(tree_entry, full_path.buf);
	}

	for (file_entry = tree->file_entry; file_entry;
	     file_entry = file_entry->next) {
		/* show this file entry */
		fprintf(stderr, "%06o %s %s %s%s%s\n", file_entry->mode,
			type_name(object_type(file_entry->mode)),
			oid_to_hex(&file_entry->oid), full_path.buf,
			full_path.len ? "/" : "", file_entry->name);
	}

	strbuf_release(&full_path);
	strbuf_release(&mark);
	return 0;
}

static int do_ls_tree_path(struct lazy_tree *root_tree, const char *path)
{
	struct lazy_tree *tree;
	struct strbuf buf = STRBUF_INIT;
	int len;
	int ret;

	/* The input ppath is the tree we want to show, get the tree. */
	if (walk_tree(root_tree, path, &tree, 0))
		return -1;

	/* We should pass the parent_dir of the tree to do_ls_tree(). */
	len = strlen(path);
	while (len > 0 && path[len - 1] == '/')
		len--;
	while (len > 0 && path[len - 1] != '/')
		len--;
	while (len > 0 && path[len - 1] == '/')
		len--;
	strbuf_add(&buf, path, len);

	ret = do_ls_tree(tree, (const char *)buf.buf);

	strbuf_release(&buf);
	return ret;
}

static int do_rm_entry(struct lazy_tree *root_tree, const char *path, int force,
		       struct object_entry **deleted)
{
	struct strbuf buf = STRBUF_INIT;
	struct lazy_tree *tree;
	char *p;
	int len;
	struct lazy_tree **tree_entry;
	struct file_entry **file_entry;
	int ret = 0;

	/* walk to parent dir */
	len = strlen(path);
	while (len > 0 && path[len - 1] == '/')
		len--;
	while (len > 0 && path[len - 1] != '/')
		len--;
	strbuf_add(&buf, path, len);
	if (walk_tree(root_tree, buf.buf, &tree, MARK_TREE_DIRTY)) {
		ret = -1;
		goto cleanup;
	}

	/* find matched entry, and marked as deleted */
	strbuf_reset(&buf);
	p = (char *)path + len;
	len = strlen(p);
	while (len > 0 && p[len - 1] == '/')
		len--;
	strbuf_add(&buf, p, len);

	tree_entry = &tree->dir_entry;
	while (*tree_entry) {
		if (!strcmp(buf.buf, (*tree_entry)->name)) {
			struct lazy_tree *next = (*tree_entry)->next;

			(*deleted)->mode = S_IFDIR;
			oidcpy(&(*deleted)->oid,
			       &(*tree_entry)->tree.object.oid);
			(*deleted)->path = xstrdup(path);
			(*tree_entry)->dirty = 1;

			free_one_tree_entry(*tree_entry);
			*tree_entry = next;
			goto cleanup;
		}
		tree_entry = &(*tree_entry)->next;
	}

	file_entry = &tree->file_entry;
	while (*file_entry) {
		if (!strcmp(buf.buf, (*file_entry)->name)) {
			struct file_entry *next = (*file_entry)->next;

			(*deleted)->mode = (*file_entry)->mode;
			oidcpy(&(*deleted)->oid, &(*file_entry)->oid);
			(*deleted)->path = xstrdup(path);

			free_one_file_entry(*file_entry);
			*file_entry = next;
			goto cleanup;
		}
		file_entry = &(*file_entry)->next;
	}

	if (!force)
		ret = error("rm: %s: no such file or directory", path);

cleanup:
	strbuf_release(&buf);
	return ret;
}

static int do_rm(struct lazy_tree *root_tree, const char *buf)
{
	struct object_entry *deleted;
	const char *path;
	int force = 0;
	int ret;

	deleted = xcalloc(1, sizeof(*deleted));

	/*
	 * Format:
	 *     [-f] SP name
	 */
	if (skip_prefix(buf, "-f ", &path))
		force = 1;
	else
		path = buf;

	ret = do_rm_entry(root_tree, path, force, &deleted);
	free_obj_entry(deleted);
	return ret;
}

static int do_add_entry(struct lazy_tree *root_tree, unsigned mode,
			struct object_id *oid, const char *path, int force)
{
	struct strbuf buf = STRBUF_INIT;
	struct lazy_tree *tree;
	char *p;
	int len;
	struct lazy_tree **tree_entry;
	struct file_entry **file_entry;
	int ret = 0;
	enum object_type type;

	/* We check availability of oid except for submodules */
	type = object_type(mode);
	if (type != OBJ_COMMIT) {
		unsigned long unused;
		int obj_type;
		obj_type = oid_object_info(the_repository, oid, &unused);
		if (obj_type < 0)
			die("object %s is missing for path: %s",
			    oid_to_hex(oid), path);
		if (type != obj_type)
			die("unmatched types (actual: %s, want: %s)",
			    type_name(obj_type), type_name(type));
	}

	/* walk to parent dir */
	len = strlen(path);
	while (len > 0 && path[len - 1] == '/')
		len--;
	while (len > 0 && path[len - 1] != '/')
		len--;
	strbuf_add(&buf, path, len);
	if (walk_tree(root_tree, buf.buf, &tree, MARK_TREE_DIRTY))
		return -1;

	/* save entry name in buf */
	strbuf_reset(&buf);
	p = (char *)path + len;
	len = strlen(p);
	while (len > 0 && p[len - 1] == '/')
		len--;
	strbuf_add(&buf, p, len);

	/* add a tree entry */
	if (type == OBJ_TREE) {
		/* walk file_entry to find D/F conflict */
		for (struct file_entry *fe = tree->file_entry; fe;
		     fe = fe->next) {
			if (!strcmp(fe->name, buf.buf)) {
				ret = error(
					"found a D/F conflict: has a file named '%s'",
					buf.buf);
				goto cleanup;
			}
		}

		tree_entry = &tree->dir_entry;
		while (*tree_entry) {
			if (!strcmp(buf.buf, (*tree_entry)->name)) {
				if (oideq(&(*tree_entry)->tree.object.oid,
					  oid)) {
					if (!force)
						warning("already exist, ignored: %s",
							path);
					break;
				}
				if (force) {
					/* remove old tree_entry */
					struct lazy_tree *next =
						(*tree_entry)->next;
					free_one_tree_entry(*tree_entry);
					*tree_entry = next;
					/* Continue loop, until we cannot find a
					 * match entry. */
					continue;
				}
				ret = error(
					"found a conflict tree with different oid, please use replace command for it: %s",
					path);
				goto cleanup;
			}
			tree_entry = &(*tree_entry)->next;
		}
		/* not exist, add tree */
		if (!*tree_entry)
			*tree_entry = new_lazy_tree(buf.buf, oid, 0);
	}
	/* add a file entry */
	else {
		/* walk dir_entry to find D/F conflict */
		for (struct lazy_tree *entry = tree->dir_entry; entry;
		     entry = entry->next) {
			if (!strcmp(entry->name, buf.buf)) {
				ret = error(
					"found a D/F conflict: has a tree named '%s'",
					buf.buf);
				goto cleanup;
			}
		}

		for (file_entry = &tree->file_entry; *file_entry;
		     file_entry = &(*file_entry)->next) {
			if (!strcmp(buf.buf, (*file_entry)->name)) {
				if ((*file_entry)->mode == mode &&
				    oideq(&(*file_entry)->oid, oid)) {
					if (!force)
						warning("already exist, ignored: %s",
							path);
					break;
				}
				if (force) {
					(*file_entry)->mode = mode;
					(*file_entry)->oid = *oid;
					break;
				}
				ret = error(
					"found a conflict entry with different mode or oid, please use replace command for it: %s",
					path);
				goto cleanup;
			}
		}
		/* not exist, add tree */
		if (!*file_entry) {
			*file_entry = xcalloc(1, sizeof(struct file_entry));
			(*file_entry)->mode = mode;
			(*file_entry)->oid = *oid;
			(*file_entry)->name = xstrdup(buf.buf);
		}
	}

cleanup:
	strbuf_release(&buf);
	return ret;
}

static int do_add(struct lazy_tree *root_tree, const char *buf)
{
	const char *ptr;
	const char *path, *p;
	char *ntr;
	unsigned mode;
	struct object_id oid;
	int force = 0;

	/*
	 * Format:
	 *     [-f] mode SP sha SP name
	 */
	if (skip_prefix(buf, "-f ", &ptr))
		force = 1;
	else
		ptr = buf;
	mode = strtoul(ptr, &ntr, 8);
	if (ptr == ntr || !ntr || *ntr != ' ')
		die("bad input for add: %s", buf);
	ptr = ntr + 1; /* sha */
	ntr = strchr(ptr, ' ');
	if (!ntr || parse_oid_hex(ptr, &oid, &p) || *p != ' ')
		die("bad input for add: %s", buf);
	path = p + 1;

	return do_add_entry(root_tree, mode, &oid, path, force);
}

static int do_add_tree(struct lazy_tree *root_tree, const char *buf)
{
	const char *ptr;
	const char *path, *p;
	struct object_id oid;
	int force = 0;

	/*
	 * Format:
	 *     [-f] SP sha SP name
	 */
	if (skip_prefix(buf, "-f ", &ptr))
		force = 1;
	else
		ptr = (char *)buf;
	if (parse_oid_hex(ptr, &oid, &p) || *p != ' ')
		die("bad input for add-tree: %s", buf);
	path = p + 1;

	return do_add_entry(root_tree, S_IFDIR, &oid, path, force);
}

static int do_replace_entry(struct lazy_tree *root_tree, unsigned mode,
			    struct object_id *oid, const char *path, int force)
{
	struct object_entry *deleted;
	int ret = 0;
	deleted = xcalloc(1, sizeof(*deleted));

	if (do_rm_entry(root_tree, path, force, &deleted)) {
		ret = -1;
		goto cleanup;
	}

	if (!mode)
		mode = deleted->mode;

	if (!mode)
		die("objects that do not exist cannot inherit mode: %s", path);

	if (do_add_entry(root_tree, mode, oid, path, force)) {
		ret = -1;
		goto cleanup;
	}

cleanup:
	free_obj_entry(deleted);
	return ret;
}

static int do_replace(struct lazy_tree *root_tree, const char *buf)
{
	const char *ptr;
	const char *path, *p;
	char *ntr;
	unsigned mode;
	struct object_id oid;
	int force = 0;

	/*
	 * Format:
	 *     [-f] SP mode SP sha SP name
	 */
	if (skip_prefix(buf, "-f ", &ptr))
		force = 1;
	else
		ptr = buf;

	mode = strtoul(ptr, &ntr, 8);
	if (ptr == ntr || !ntr || *ntr != ' ')
		die("bad input for add: %s", buf);
	ptr = ntr + 1; /* sha */
	ntr = strchr(ptr, ' ');
	if (!ntr || parse_oid_hex(ptr, &oid, &p) || *p != ' ')
		die("bad input for add: %s", buf);
	path = p + 1;

	return do_replace_entry(root_tree, mode, &oid, path, force);
}

static int do_move_entry(struct lazy_tree *root_tree, char *source_path,
			 char *destination_path, const int force)
{
	struct strbuf buf = STRBUF_INIT;
	struct object_entry *source_entry, *destination_entry;
	unsigned int len;
	int ret = 0;
	char *source_file_name;
	enum object_type source_type, destination_type;
	char *s = source_path, *d = destination_path;
	struct object_entry *deleted;

	source_entry = xcalloc(1, sizeof(struct object_entry));
	destination_entry = xcalloc(1, sizeof(struct object_entry));
	deleted = xcalloc(1, sizeof(struct object_entry));

	len = strlen(source_path);
	source_file_name = xstrdup(basename(source_path));

	if (read_entry(root_tree, source_path, source_entry))
		source_entry = NULL;

	if (read_entry(root_tree, destination_path, destination_entry))
		destination_entry = NULL;

	if (is_empty_obj_entry(source_entry))
		die(_("source path does not exist: %s"), source_path);

	/* Check if the destination is a sub folder of the source */
	if (!strncmp(source_path, destination_path, len) &&
	    (destination_path[len] == '/' || destination_path[len] == '\0'))
		die(_("cannot move a folder to its sub folder, source: %s, destination: %s"),
		    source_path, destination_path);

	/* Just add to the new path, and remove the old path */
	if (is_empty_obj_entry(destination_entry))
		goto action;

	source_type = object_type(source_entry->mode);
	destination_type = object_type(destination_entry->mode);

	if (source_type == OBJ_TREE)
		if (destination_type == OBJ_BLOB)
			die(_("cannot move a folder to a file, source: %s, destination: %s"),
			    source_path, destination_path);

	/* Move the file to the destination folder */
	if (destination_type == OBJ_TREE) {
		strbuf_add(&buf, destination_path, strlen(destination_path));
		strbuf_addf(&buf, "/%s", source_file_name);
		d = buf.buf;

		goto action;
	}

action:
	if (do_add_entry(root_tree, source_entry->mode, &source_entry->oid, d,
			 force)) {
		ret = -1;
		goto cleanup;
	}

	if (do_rm_entry(root_tree, s, force, &deleted)) {
		ret = -1;
		goto cleanup;
	}

cleanup:
	free(source_entry);
	free(destination_entry);
	free(source_file_name);
	strbuf_release(&buf);
	free_obj_entry(deleted);

	return ret;
}

static int do_move(struct lazy_tree *root_tree, const char *parameters)
{
	const char *ptr;
	char *source_path, *destination_path;
	int force = 0;
	struct string_list list = STRING_LIST_INIT_DUP;
	int ret = 0;

	/*
	 * Format:
	 *     [-f] SP source SP destination
	 */
	if (skip_prefix(parameters, "-f ", &ptr))
		force = 1;
	else
		ptr = (char *)parameters;

	string_list_split(&list, ptr, ' ', -1);

	if (list.nr != 2)
		die("bad input for move: %s", parameters);

	source_path = list.items[0].string;
	destination_path = list.items[1].string;

	ret = do_move_entry(root_tree, source_path, destination_path, force);

	string_list_clear(&list, 0);
	return ret;
}

static void append_to_tree(int *idx, unsigned mode, struct object_id *oid,
			   char *path)
{
	struct treeent *ent;
	if (strchr(path, '/'))
		die("path %s contains slash", path);

	ent = xcalloc(1, sizeof(*ent));
	ent->name = path;
	ent->len = strlen(path);
	ent->mode = mode;
	ent->oid = oid;

	ALLOC_GROW(entries, *idx + 1, alloc);
	entries[(*idx)++] = ent;
}

static int ent_compare(const void *a_, const void *b_)
{
	struct treeent *a = *(struct treeent **)a_;
	struct treeent *b = *(struct treeent **)b_;
	return base_name_compare(a->name, a->len, a->mode, b->name, b->len,
				 b->mode);
}

static int rehash_tree(struct lazy_tree *tree)
{
	struct lazy_tree *tree_entry;
	struct file_entry *file_entry;
	int used = 0;
	size_t size;
	int i;
	struct strbuf buf = STRBUF_INIT;

	for (tree_entry = tree->dir_entry; tree_entry;
	     tree_entry = tree_entry->next) {
		if (is_empty_tree(tree_entry))
			continue;
		append_to_tree(&used, S_IFDIR, &tree_entry->tree.object.oid,
			       tree_entry->name);
	}

	for (file_entry = tree->file_entry; file_entry;
	     file_entry = file_entry->next) {
		append_to_tree(&used, file_entry->mode, &file_entry->oid,
			       file_entry->name);
	}

	QSORT(entries, used, ent_compare);
	for (size = i = 0; i < used; i++)
		size += 32 + entries[i]->len;

	strbuf_init(&buf, size);
	for (i = 0; i < used; i++) {
		struct treeent *ent = entries[i];
		strbuf_addf(&buf, "%o %s%c", ent->mode, ent->name, '\0');
		strbuf_add(&buf, ent->oid->hash, the_hash_algo->rawsz);
	}

	write_object_file(buf.buf, buf.len, OBJ_TREE, &tree->tree.object.oid);
	strbuf_release(&buf);
	tree->dirty = 0;
	/* Make place-holder tree as loaded to prevent reload with duplicate
	 * entries */
	tree->loaded = 1;

	for (i = 0; i< used; i++)
		FREE_AND_NULL(entries[i]);

	return 0;
}

static int do_commit(struct lazy_tree *tree)
{
	struct lazy_tree **tree_entry;
	int ret = 0;

	if (!tree->dirty)
		return 0;

	tree_entry = &tree->dir_entry;
	while (*tree_entry) {
		/* Remove empty subdir */
		if (is_empty_tree(*tree_entry)) {
			struct lazy_tree *next;
			next = (*tree_entry)->next;
			free_one_tree_entry(*tree_entry);
			*tree_entry = next;
			continue;
		}
		/* Commit dirty subdir */
		if ((*tree_entry)->dirty) {
			ret = do_commit(*tree_entry);
			if (ret)
				break;
		}
		tree_entry = &(*tree_entry)->next;
	}
	if (!ret)
		ret = rehash_tree(tree);
	return ret;
}

int cmd_edit_tree(int argc, const char **argv, const char *prefix)
{
	const char *input = NULL;
	FILE *reader;
	struct strbuf sb = STRBUF_INIT;
	struct object_id oid;
	int nul_term_line = 0;
	strbuf_getline_fn getline_fn;
	struct lazy_tree *root_tree = xcalloc(1, sizeof(struct lazy_tree));
	struct tree *tree;
	int ret = 0;

	const struct option edit_tree_options[] = {
		OPT_BOOL('z', NULL, &nul_term_line,
			 N_("input is NUL terminated")),
		OPT_FILENAME('f', "filename", &input, "read input from file"),
		OPT_END()
	};

	git_config(git_default_config, NULL);

	argc = parse_options(argc, argv, prefix, edit_tree_options,
			     edit_tree_usage, 0);
	getline_fn = nul_term_line ? strbuf_getline_nul : strbuf_getline_lf;

	if (argc < 1)
		usage_with_options(edit_tree_usage, edit_tree_options);

	if (repo_get_oid(the_repository, argv[0], &oid))
		die("Not a valid object name %s", argv[0]);

	/* Get tree object from commit or tag */
	tree = parse_tree_indirect(&oid);
	if (!tree)
		die("not a tree object: %s", argv[0]);

	/* Fill tree buffer with tree object's raw content. */
	root_tree->tree.object.oid = tree->object.oid;
	if (parse_tree(&root_tree->tree))
		die("not a tree object: %s", argv[0]);

	/* Read tree and fill file entries and direct subtree. */
	if (load_one_tree_entry(root_tree))
		return -1;

	if (input) {
		reader = fopen(input, "r");
		if (!reader)
			die_errno("fail to open %s", input);
	} else {
		reader = stdin;
	}

	while (getline_fn(&sb, reader) != EOF) {
		const char *p;

		if (*sb.buf == '#' || !*sb.buf)
			continue;
		if (skip_prefix(sb.buf, "walk ", &p))
			ret = walk_tree(root_tree, p, NULL, 0);
		else if (skip_prefix(sb.buf, "ls-tree ", &p))
			ret = do_ls_tree_path(root_tree, p);
		else if (!strcmp(sb.buf, "ls-tree"))
			ret = do_ls_tree_path(root_tree, "");
		else if (skip_prefix(sb.buf, "echo ", &p))
			fprintf(stderr, "%s\n", p);
		else if (!strcmp(sb.buf, "echo"))
			fprintf(stderr, "\n");
		else if (skip_prefix(sb.buf, "add ", &p))
			ret = do_add(root_tree, p);
		else if (skip_prefix(sb.buf, "add-tree ", &p))
			ret = do_add_tree(root_tree, p);
		else if (skip_prefix(sb.buf, "replace ", &p))
			ret = do_replace(root_tree, p);
		else if (skip_prefix(sb.buf, "rm ", &p))
			ret = do_rm(root_tree, p);
		else if (skip_prefix(sb.buf, "mv ", &p))
			ret = do_move(root_tree, p);
		else if (!strcmp(sb.buf, "commit"))
			ret = do_commit(root_tree);
		else
			ret = error("unknown command: %s", sb.buf);

		if (ret)
			break;
	}

	if (reader != stdin)
		fclose(reader);

	if (!ret)
		ret = do_commit(root_tree);
	if (!ret)
		printf("%s\n", oid_to_hex(&root_tree->tree.object.oid));

	strbuf_release(&sb);
	free_tree_entry_list(root_tree);
	return ret;
}
